#include "SList.h"
using namespace std;

SList::SList(SListNode *s) : sn(s)
{
}

void SList::SListPrint(SListNode *phead)
{
    //不用判空，头节点可能为NULL
    SListNode *cur = phead;
    while (cur != NULL)
    {
        cout << cur->data << "->";
        cur = cur->next;
    }
    cout << "NULL\n";
}

SList::SListNode *SList::BuySListNode(SLTDataType x)
{
    SListNode *newNode = new SListNode;
    if (newNode == NULL)
    {
        cout << "堆区已满, 开辟失败!\n";
        exit(EXIT_FAILURE);
    }
    else
    {
        newNode->data = x;
        newNode->next = NULL;
    }
}

void SList::SListPushBack(SListNode *&phead, SLTDataType x)
{
    // assert(phead);
    //开辟新节点
    SListNode *newNode = BuySListNode(x);
    if (phead == NULL)
    {
        phead = newNode;
    }
    else
    {
        //找尾
        SListNode *tail = phead;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        //链接新节点
        tail->next = newNode;
    }
}

void SList::SListPopBack(SListNode *&phead)
{
    if (phead == NULL)
    {
        //如果链表为空，则没有内容删除，直接返回
        return;
    }
    else if (phead->next == NULL)
    {
        //如果链表只有一个节点，则删除第一个节点，然后让头节点指向NULL
        delete phead->next;
        phead = NULL;
    }
    else
    {
        //找尾
        SListNode *tail = phead;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        delete (tail->next);
        tail->next = NULL;
    }
}

void SList::SListInsert(SListNode *&phead, SListNode *pos, SLTDataType x)
{
    assert(pos);
    if (phead == NULL)
    {
        return;
    }
    //如果pos是第一个节点，则直接调用头插接口
    if (pos == phead)
    {
        SListPushFront(phead, x);
    }
    else
    {
        SListNode *newNode = BuySListNode(x);
        SListNode *prve = phead;
        //找pos前一个节点
        while (prve->next != pos)
        {
            prve = prve->next;
        }
        prve->next = newNode;
        newNode->next = pos;
    }
}

void SList::SListPushFront(SListNode *&phead, SLTDataType x)
{
    SListNode *newNode = BuySListNode(x);
    newNode->next = phead;
    phead = newNode;
}

void SList::SListPopFront(SListNode *&phead)
{
    if (phead == NULL)
    {
        return;
    }
    else
    {
        SListNode *next = phead->next;
        // phead相当于第一个节点的空间
        delete phead;
        phead = next;
    }
}

SList::SListNode *SList::SListFind(SListNode *phead, SLTDataType x)
{
    if (phead == NULL)
    {
        return NULL;
    }
    else
    {
        SListNode *cur = phead;
        while (cur != NULL)
        {
            if (cur->data == x)
            {
                return cur;
            }
            cur = cur->next;
        }
        return NULL;
    }
}

void SList::SListInsertAfter(SListNode *pos, SLTDataType x)
{
    assert(pos);
    SListNode *newNode = BuySListNode(x);
    newNode->next = pos->next;
    pos->next = newNode;
}

void SList::SListErase(SListNode *&phead, SListNode *pos)
{
    assert(pos);
    if (phead == NULL)
    {
        return;
    }
    if (phead == pos)
    {
        SListPopFront(phead);
    }
    else
    {
        SListNode *prev = phead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        delete pos;
        pos = NULL;
    }
}

void SList::SListEraseAfter(SListNode *pos)
{
    assert(pos);
    SListNode *next = pos->next;
    if (next != NULL)
    {
        pos->next = next->next;
        delete next;
        next = NULL;
    }
    else
    {
        return;
    }
}

void SList::SListDestory(SListNode *&phead)
{
    delete[] phead;
    phead = NULL;
}

int main()
{
    SList s1;
    //尾插
    s1.SListPushBack(s1.sn, 1);
    s1.SListPushBack(s1.sn, 2);
    s1.SListPushBack(s1.sn, 3);
    s1.SListPushBack(s1.sn, 4);
    s1.SListPushBack(s1.sn, 5);

    s1.SListPrint(s1.sn);

    //头插
    s1.SListPopBack(s1.sn);
    s1.SListPushFront(s1.sn, 0);
    s1.SListPushFront(s1.sn, -1);
    s1.SListPushFront(s1.sn, -2);
    s1.SListPrint(s1.sn);

    //头删
    s1.SListPopFront(s1.sn);
    s1.SListPopFront(s1.sn);
    s1.SListPrint(s1.sn);

    //查找
    SList s2;
    s2.sn = s1.SListFind(s1.sn, 3);
    if (s2.sn == NULL)
    {
        cout << "很遗憾, 没有找到....\n";
    }
    else
    {
        cout << "恭喜,找到了!!! ---> 这个值是: " << s2.sn->data << endl;
    }

    //随机插入
    s1.SListInsert(s1.sn, s2.sn, 100); //在3的前面插入数据100
    s1.SListPrint(s1.sn);

    //在pos位置后面插入
    s1.SListInsertAfter(s2.sn, 200);
    s1.SListPrint(s1.sn);

    //删除pos位置的节点
    s1.SListErase(s1.sn, s2.sn);
    s1.SListPrint(s1.sn);

    //删除pos位置后的节点
    SList s3;
    s3.sn = s3.SListFind(s1.sn, 200);
    s1.SListEraseAfter(s3.sn);
    s1.SListPrint(s1.sn);

    //释放链表
    s1.SListDestory(s1.sn);
    s1.SListPrint(s1.sn);
    system("pause");
    return 0;
}